|
The following variant of the fair cake-cutting problem was introduced by Ted Hill in 1983. There is a territory ''D'' adjacent to ''n'' countries. Each country values the different subsets of ''D'' differently. The countries would like to divide ''D'' fairly among them, where "fair" means a proportional division. Additionally, ''the share allocated to each country must be connected and adjacent to that country''. This geographic constraint distinguishes this problem from classic fair cake-cutting. Formally, every country ''Ci'' must receive a disjoint piece of ''D'', marked ''Di'', such that a portion of the border between ''Ci'' and ''D'' is contained in the interior of ''Ci ∪ Di''. == Impossibility and possibility == There are cases in which the problem cannot be solved: 1. If there is a single point to which two countries assign all their value (e.g. a holy place), then obviously the territory cannot be divided proportionally. To prevent such situations, we assume that all countries assign a value of 0 to all singular points. 2. If ''D'' is a square, there are 4 countries adjacent to the 4 sides of the square, and each country assigns all its value to the border at the opposite side, then every allocation that connects, say, the northern country with its desired southern border will make it impossible to connect the eastern country with its desired western border (as long as we are in a two-dimensional plane). To prevent such situations, we assume that all countries assign a value of 0 to the boundary of ''D''. In 1983, Hill proved that, if each single point in ''D'' has a value of 0 for all countries, and the boundary of ''D'' has a value of 0 for all countries, then there exists a proportional division with the adjacency constraint. His proof was only existential – no algorithm was described.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hill–Beck land division problem」の詳細全文を読む スポンサード リンク
|